//Stack implementation using a linked list, uses a header node


#include "stdio.h"
#include "stdlib.h"

typedef int elementType;

struct node{
	elementType element;
	struct node *next;
};

typedef struct node* ptrToNode;
typedef ptrToNode stack;


stack createStack(void);
void disposeStack(stack s);
int isEmpty(stack s);
void makeEmpty(stack s);
int push(stack s, elementType x);
elementType pop(stack s);
elementType top(stack s);



stack createStack(void){
	stack s = (ptrToNode)malloc(sizeof(struct node));
	if(s){
		s->next = NULL;
		return s;
	}
	
	return NULL;
}


//Must modify calling function's stack hdr node address holder(ptr)
void disposeStack(stack *ps)
{
	if(ps){
		makeEmpty((*ps));	
		free((*ps)); //free the header node that the header node ptr is pointing to
		*ps = NULL; //set the header node ptr to NULL in the calling function(using address of the hdr node ptr i.e. a ptr to ptr)
	}
}


int isEmpty(stack s)
{
	if(s && s->next == NULL)
		return 1;
	else
		return 0;
}


void makeEmpty(stack s)
{
	ptrToNode p, q;
	
	if(!s)
		return;
	
	p = s->next;
	while(p){
		printf("freeing : %d\n", p->element);
		
		q = p->next;
		free(p);
		p = q;
	}

	s->next = NULL;
	
}


int push(stack s, elementType x)
{
	if(!s)
		return 0;
	
	ptrToNode p = (ptrToNode)malloc(sizeof(struct node));

	if(p){
		p->element = x;
		p->next = s->next;
		s->next = p;
		return 1;
	}	

	return 0;
}


//What about empty stack, how to signal it ?
elementType pop(stack s)
{
	if(!s)
		return 0;
	
	ptrToNode p = s->next;
	elementType x;

	if(p){
		x = p->element;
		s->next = p->next;
		free(p);
		return x;
	}	

	return 0;
}


elementType top(stack s)
{
	if(s && s->next)
		return s->next->element;

	return 0;
}


int main(int argc, char* argv[])
{
	stack s = createStack();
	int i;

	for(i=0; i<10; i++)
		push(s, i);

	//makeEmpty(s);

	disposeStack(&s);

	for(i=0; i<5; i++)
		printf("Top: %d\n", top(s));
	
	for(i=0; i<11; i++)
		printf("Pop: %d\n", pop(s));

			
	return 0;
}

